package test.n00300;


import java.util.ArrayList;
import java.util.List;

public class Problem00390 {
    public static void main(String[] args) {
        println(new int[]{2, 3, 6, 7}, 7);
    }

    public static void println(int[] candidates, int target) {
        Solution ss = new Solution();
        System.out.println(candidates + "," + target + "," + ss.combinationSum(candidates, target));
    }

    private static class Solution {

        /**
         * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
         * <p>
         * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
         * <p>
         * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/combination-sum
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 解题思路:
         * 排列 + 暴力
         *
         * @param candidates
         * @param target
         * @return
         */
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> combine = new ArrayList<>();
            dfs(candidates, target, 0, combine, result);
            return result;
        }

        public void dfs(int[] candidates, int target, int begin, List<Integer> combine, List<List<Integer>> result) {
            if (candidates.length == begin) {
                return;
            }

            if (target == 0) {
                result.add(new ArrayList<>(combine));
                return;
            }

            dfs(candidates, target, begin + 1, combine, result);

            if (candidates[begin] <= target) {
                combine.add(candidates[begin]);
                dfs(candidates, target - candidates[begin], begin, combine, result);
                combine.remove(combine.size() - 1);
            }
        }
    }
}
